#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// 利用了贪心的思想，每次走当前能跳到的最大值
// 然后再加上层序遍历的思想，将最小跳跃问题转换成bfs求最短路径问题
class Solution {
public:
    // 到达nums[n - 1] 的最小跳跃次数
    // 如何做呢？
    // 每次跳跃最长肯定不行
    // 方法一: 动态规划
    // 方法二: 用类似层序遍历的做法，每次把能够跳跃的区间范围找出来
    int jump(vector<int>& nums) {
        int l = 0, r = 0;
        int ans = 0;
        // 当已经可以达到最右边时，中止循环
        while(r < nums.size() - 1)
        {
            ++ans;
            int next_l = r + 1, next_r = 0;
            for(int i = l; i <= r; ++i)
                next_r = max(next_r, i + nums[i]);
            l = next_l, r = next_r;
        }
        return ans;
    }
};